#ifndef __DLX_SOLVER_H__
#define __DLX_SOLVER_H__
/*
Source Code

Problem: 3074  User: theorix 
Memory: 308K  Time: 47MS 
Language: C++  Result: Accepted 

Source Code 
*/
//Add this enlarge STACK size for Visual C++
//#pragma comment(linker,"/STACK:102400000,1024000")
#include <string.h> //for memset()
#include<iostream>
#include <vector>
using namespace std;
#define RR 729
#define CC 324
#define INF 1000000000

//应该单独包含到一个cpp文件里用cl.exe编译试试

class dlx_solver
{
private:
	int mem[RR+9];
	int ans[RR+9];
	char ch[RR+9];
	int cnt[CC+9];
	struct node
	{
		int r,c;
		node *up;
		node *down;
		node *left;
		node *right;
	}head,row[RR],col[CC];//,all[RR*CC+99];
	int all_t;

    node *all;
	bool chk_unique ;
public:
	int scount;

public:
	int solution_count(string str)
	{
		chk_unique=true;
		scount=0;
		run(str);
		return scount;
	}
	string do_solve(string str)
	{
		chk_unique = false;
		scount=0;
		string ret=run(str);
		if (scount != 1)
			return "";
		return ret;
	}
	dlx_solver():
        scount(0)
	{
		all=new node[RR*CC+99];
	}
	~dlx_solver()
	{
		delete[] all;
	}

private:
	inline void link(int r,int c)
	{
		cnt[c]++;
		node *t=&all[all_t++];
		t->r=r;
		t->c=c;
		t->left=&row[r];
		t->right=row[r].right;
		t->left->right=t;
		t->right->left=t;
		t->up=&col[c];
		t->down=col[c].down;
		t->up->down=t;
		t->down->up=t;
	}
	inline void remove(int c)
	{
		node *t,*tt;
		col[c].right->left=col[c].left;
		col[c].left->right=col[c].right;
		for(t=col[c].down;t!=&col[c];t=t->down)
		{
			for(tt=t->right;tt!=t;tt=tt->right)
			{
				cnt[tt->c]--;
				tt->up->down=tt->down;
				tt->down->up=tt->up;
			}
			t->left->right=t->right;
			t->right->left=t->left;
		}
	}
	inline void resume(int c)
	{
		node *t,*tt;
		for(t=col[c].down;t!=&col[c];t=t->down)
		{        
			t->right->left=t;
			t->left->right=t;
			for(tt=t->left;tt!=t;tt=tt->left)
			{
				cnt[tt->c]++;
				tt->down->up=tt;
				tt->up->down=tt;
			}
		}    
		col[c].left->right=&col[c];
		col[c].right->left=&col[c];
	}
	int solve(int k)
	{
		if(head.right==&head)
			return true;
		node*t,*tt;
		int min=INF,tc;
		for(t=head.right;t!=&head;t=t->right)
		{
			if(cnt[t->c]<min)
			{
				min=cnt[t->c];
				tc=t->c;
				if(min<=1)break;
			}
		}
		remove(tc);
		int scnt=0;
		for(t=col[tc].down;t!=&col[tc];t=t->down)
		{
			mem[k]=t->r;
			t->left->right=t;
			for(tt=t->right;tt!=t;tt=tt->right)
			{
				remove(tt->c);
			}
			t->left->right=t->right;

			//if(solve(k+1))
			//	return true;

			scnt+=solve(k+1);
			if (!chk_unique && scnt ==1)
				return scnt;
			if (scnt > 1)
				return scnt;
			//继续找下一个可能


			t->right->left=t;
			for(tt=t->left;tt!=t;tt=tt->left)
			{
				resume(tt->c);
			}
			t->right->left=t->left;
		}
		resume(tc);
		return false;
	}

	string run(string str)
	{
		const char *ch=str.c_str();
		int i;
		all_t=1;
		memset(cnt,0,sizeof(cnt));
		head.left=&head;
		head.right=&head;
		head.up=&head;
		head.down=&head;
		head.r=RR;
		head.c=CC;
		for(i=0;i<CC;i++)
		{
			col[i].c=i;
			col[i].r=RR;
			col[i].up=&col[i];
			col[i].down=&col[i];
			col[i].left=&head;
			col[i].right=head.right;
			col[i].left->right=&col[i];
			col[i].right->left=&col[i];
		}
		for(i=0;i<RR;i++)
		{
			row[i].r=i;
			row[i].c=CC;
			row[i].left=&row[i];
			row[i].right=&row[i];
			row[i].up=&head;
			row[i].down=head.down;
			row[i].up->down=&row[i];
			row[i].down->up=&row[i];
		}
		for(i=0;i<RR;i++)
		{
			int r=i/9/9%9;
			int c=i/9%9;
			int val=i%9+1;
			if(ch[r*9+c]=='.'||ch[r*9+c]=='0'||ch[r*9+c]==val+'0')
			{
				link(i,r*9+val-1);
				link(i,81+c*9+val-1);
				int tr=r/3;
				int tc=c/3;
				link(i,162+(tr*3+tc)*9+val-1);
				link(i,243+r*9+c);
			}
		}
		for(i=0;i<RR;i++)
		{
			row[i].left->right=row[i].right;
			row[i].right->left=row[i].left;
		}
        // record the solution number!
		scount=solve(1);
		for(i=1;i<=81;i++)
		{
			int t=mem[i]/9%81;
			int val=mem[i]%9+1;
			ans[t]=val;
		}
		char buf[83];
		for(i=0;i<81;i++)
        {
            //printf("%d",ans[i]);
			//sprintf(buf+i,"%d",ans[i]);
			buf[i]='0'+ans[i];
        }
		buf[i]='\0';
        //printf("\n");
        //printf(buf);
		return buf;
	}

};
#endif

